/** 递增排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(logn) 递归栈
 */

const quickSort = (arr, start, end) => {
    /** 递归边界条件 */
    if(end - start < 1) return;
    /** 取第一个元素为基准 */
    const pivot = arr[start];
    // 定义双指针
    let left = start;
    let right = end;
    while(left < right) {
        // 从右往左
        while(left<right && arr[right] >= pivot) right--;
        arr[left] = arr[right];
        // 从左往右
        while(left<right && arr[left] <= pivot) left++;
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    quickSort(arr, start, left - 1);
    quickSort(arr, left + 1, end);
    return arr;
}

const arr = [2,4,5,3,1];
console.log(quickSort(arr, 0, 4));
